Advances in semi-conductor processing and logic design have permitted an increase in the amount of logic that may be present on integrated circuit devices. As a result, computer system configurations have evolved from multiple integrated circuits in a system to the capability of storing multiple architecture states on a single integrated circuit, which allows for concurrent execution of multiple threads. Therefore, a single die may have multiple resources, such as multiple cores and/or multiple threads, to execute code in parallel.
A thread typically refers to the ability of an integrated circuit to store a separate architecture state/context for each thread, which may be associated with shared execution resources. Additionally, a thread may refer to an independent application, program, or software thread that is executed on a hardware thread or core. On the other hand, a core typically refers to an independent architecture state associated with dedicated execution resources, which may be physically contiguous and logically partitioned or physically separate. Yet, both a core and a thread may share some level of cache in a memory hierarchy, as well as other units, such as bus interface to communicate with external devices.
The use of one or more cache memory systems within a computer's memory hierarchy is a well-known technique to increase the performance of a computer. Traditionally, there have been three types of cache organizations that have been used: the fully associative, the k-way set associative; and the direct mapped cache organizations. In a fully associative cache organization, each item of information from a main system memory is able to be stored in any cache entry. In contrast, in a set associative cache, the cache is logically broken up into k banks of memory, i.e. k ways. A set associative cache “associates” the locations within a logically viewed page of memory to a corresponding cache line in each of the k ways based on an offset of the memory location within the page of memory. Therefore, every memory location corresponds to a “set” of cache lines within the k-ways. Similarly, a direct mapped cache is effectively a one way set associative cache associating memory locations to a cache line within the one way of the direct mapped cache.
During a memory transfer, a resource or processor generates a memory address, which references a location of an element. The term resource, referring to a core, execution core, hardware thread, software thread, or other threading technique. An element being an instruction or operand. A cache associated with the resource or processor is checked to determine if the element is present in cache or must be retrieved from system memory. Typical cache implementations using tag lookups, indexes, etc. are used to determine if the element is present in the cache. A cache hit refers to a determination that the element is present in cache. Alternatively, if the element requested is not present in cache, a cache miss results and the element is retrieved from a main system memory to replace the contents of a cache line within the cache. The process of replacement of an existing line to make space for a recent miss is also called as cache-line victimization.
Shared caches among multiple resources allow different independent program threads to share data and instructions without having duplicate misses to the cache. However, multiple resources sharing a cache may result in destructive interference if one resource victimizes much of the cache state belonging to another resource. An example of multiple resources sharing a single cache is illustrated in FIG. 1. Integrated circuit 140 comprises resource 145, resource 150, and Nth resource 155. Resources 145-155 share access to cache 160, which is organized as a four way set associative cache having ways 165-168. As can be seen, one of the resources 145-155, such as resource 150, may begin to monopolize cache 160 and victimize much of the cache state belonging to resource 145. Therefore, ensuring fairness across multiple resources becomes an important consideration.